package thinking.backtracking;

/**
 * 使用备忘录优化PackageQuestion
 *
 * @author yeyangtao created at 15:24 2020/10/29
 */
public class PackageQuestion1 {
    //结果放到maxW中
    private int maxW = Integer.MIN_VALUE;
    //物品重量
    private final int[] weight = {2, 2, 4, 6, 3};
    //物品个数
    private final int n = 5;
    //背包承受的最大重量
    private final int w = 9;
    //可能会存在f(n,m)重复计算的情况，将已经计算的保存起来
    private boolean[][] mem = new boolean[5][10];

    /**
     * f(0,0)调用
     *
     * @param i  物品编号
     * @param cw 当前背包重量
     */
    public void f(int i, int cw) {
        //达到了最大重量 或者放完了物品
        if (cw == w || i == n) {
            if (cw > maxW) maxW = cw;
            return;
        }
        if (mem[i][cw]) return; // 重复状态
        mem[i][cw] = true; // 记录(i, cw)这个状态

        //不装第i个物品
        f(i + 1, cw);
        if (cw + weight[i] <= w) {
            f(i + 1, cw + weight[i]);
        }
    }
}
